For many practical applications of ASP, for instance data integration orplanning, query answering is important, and therefore query optimizationtechniques for ASP are of great interest. Magic Sets are one of thesetechniques, originally defined for Datalog queries (ASP without disjunction andnegation). Dynamic Magic Sets (DMS) are an extension of this technique, whichhas been proved to be sound and complete for query answering over ASP programswith stratified negation. A distinguishing feature of DMS is that the optimization can be exploitedalso during the nondeterministic phase of ASP engines. In particular, aftersome assumptions have been made during the computation, parts of the programmay become irrelevant to a query under these assumptions. This allows fordynamic pruning of the search space, which may result in exponentialperformance gains. In this paper, the correctness of DMS is formally established and proved forbrave and cautious reasoning over the class of super-consistent ASP programs(ASP^{sc} programs). ASP^{sc} programs guarantee consistency (i.e., have answersets) when an arbitrary set of facts is added to them. This result generalizesthe applicability of DMS, since the class of ASP^{sc} programs is richer thanASP programs with stratified negation, and in particular includes allodd-cycle-free programs. DMS has been implemented as an extension of DLV, andthe effectiveness of DMS for ASP^{sc} programs is empirically confirmed byexperimental results with this system.
展开▼
